package algorithm.leetcode.I1to100;

/**
 * 题目保证了没有重复元素
 * 所以不会有歧义
 */

public class Q35 {

    /**
     * 寻找单调数组中第一个不小于target的数
     * 这个搜索的另一个含义是 nums 中小于 target 的元素有多少个
     * 比如对于有序数组 nums = [2,3,5,7], target = 1，算法会返回 0，含义是：nums 中小于 1 的元素有 0 个
     * 再比如说 nums = [2,3,5,7], target = 8，算法会返回 4，含义是：nums 中小于 8 的元素有 4 个
     * 综上可以看出，函数的返回值（即 left 变量的值）取值区间是闭区间 [0, nums.length]，故 right 初始化为 nums.length
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length;
        int mid;

        while (low < high) {
            mid = low + ((high-low)>>1);
            // 如果中间这个数比目标值大或者等于,把上界拉倒中间这个位置,并且中间这个位置可能是结果所以含在内
            if (nums[mid] >= target) high = mid;
            // 如果中间这个数比目标值小,把下界拉倒中间这个位置后面一个,并且中间这个位置不可能是结果所以去掉
            else low = mid + 1;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] ints = {1};

        Q35 threeFive = new Q35();
        System.out.println(threeFive.searchInsert(ints, -5));

    }

}
